home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 7 / Apprentice-Release7.iso / Environments / Open Prolog 1.0.3d33 / Contributions from Others / Henk Schotel / Knights Tour < prev    next >
Text File  |  1993-10-06  |  4KB  |  151 lines
  1. % SIMPLE-KNIGHTS-TOUR: Knight jumping on a 3x3 board.
  2. % From Luger & Stubblefield - AI and the Design of Expert Systems (1989).
  3. % Modified and Open Prolog graphics added by
  4. %
  5. %    Henk Schotel
  6. %    Nymegen University - Philosophy
  7. %    Postbox 9108
  8. %    NL-6500 HK Nijmegen
  9. %    The Netherlands
  10. %
  11. %    e-mail: HSCHOTEL@KUNRC1.URC.KUN.NL
  12. %
  13.  
  14. % SIMPLE-KNIGHTS-TOUR
  15. % This implements the simplified knight's tour problem from
  16. % section 6.1.2.  It uses lists to keep track of previously visited
  17. % states.
  18.  
  19. % to run it, give PROLOG a path/3 goal with the start and the goal
  20. % and a 3rd argument for the solution. For example, to test for a path
  21. % from square 2 to square 4, enter the goal: path(2, 4, R).
  22. % ?-path(2, 4, R).   % R will contain the path
  23.  
  24. %These predicates enumerate the moves of the knight's tour.
  25.  
  26. move(1,6).
  27. move(1,8).
  28. move(2,7).
  29. move(2,9).
  30. move(3,4).
  31. move(3,8).
  32. move(4,3).
  33. move(4,9).
  34. move(6,7).
  35. move(6,1).
  36. move(7,6).
  37. move(7,2).
  38. move(8,3).
  39. move(8,1).
  40. move(9,4).
  41. move(9,2).
  42.  
  43. path(P,Q,R):-
  44.         init_pen_size,
  45.         draw_board(P,Q),
  46.         path(P,Q,[P],R),
  47.         draw_path(R),
  48.         increment_pen_size. % For the next solution
  49.  
  50. % to run path/4 give PROLOG a path goal with the start, goal [and been list
  51. % instantiated to the desired values.]  For example, to test for a path
  52. % from square 2 to square 4, enter the goal: path(2, 4, [2], R ).
  53.  
  54. % the recursive path predicate controls the search
  55.  
  56. path(Z,Z,L,R) :-
  57.         reverse(L,R).
  58. path(X,Y,L,R) :-
  59.  move(X,Z),
  60.  not(member(Z,L)),
  61.  path(Z,Y,[Z|L],R).
  62.  
  63. % The member predicate tests for membership of an element in a
  64. %  list.
  65.  
  66. member(X,[X|T]).
  67. member(X,[Y|T]) :- member(X,T).
  68.  
  69. reverse(L,R):-
  70.         reverse(L,[],R).
  71.  
  72. reverse([],R,R).
  73. reverse([H|T],S,R):-
  74.         reverse(T,[H|S],R).
  75.  
  76. %-------------------------------------------------------------------------
  77. % Graphics:
  78. %-------------------------------------------------------------------------
  79.  
  80. draw_path([_]).
  81. draw_path([P,Q|Rest]):-
  82.         draw_jump(P,Q),
  83.         draw_path([Q|Rest]).
  84.  
  85. draw_jump(P,Q):-
  86.         xy(P,(Xp,Yp)),
  87.         xy(Q,(Xq,Yq)),
  88.         draw(3,line(Xp,Yp,Xq,Yq),_).
  89.  
  90. %  1  2  3
  91.  
  92. %  4  5  6
  93.  
  94. %  7  8  9
  95.  
  96. xy(1,(50,50)).
  97. xy(2,(150,50)).
  98. xy(3,(250,50)).
  99. xy(4,(50,150)).
  100. xy(5,(150,150)).
  101. xy(6,(250,150)).
  102. xy(7,(50,250)).
  103. xy(8,(150,250)).
  104. xy(9,(250,250)).
  105.  
  106. draw_board(P,Q) :-
  107.  draw(2,_,_),
  108.         draw(1,path(50,20,368,338),_),  % T,L,Hlength,VLength
  109.                                  %     (18 extra for the scroll bars!)
  110.         draw(6,line(3,3),_),            % pensize 3
  111.  draw(4,rect(0,0,303,303),_),    % 1 point of white to try and understand
  112.         draw(3,line(4,100,296,100),_),
  113.         draw(3,line(4,200,296,200),_),
  114.         draw(3,line(100,4,100,296),_),
  115.         draw(3,line(200,4,200,296),_),
  116.         draw_square(P),
  117.         draw_dot(Q),
  118.         draw(6,line(1,1),_).
  119.  
  120. draw_dot(P):-
  121.         xy(P,(X,Y)),
  122.         L is X-4,
  123.         T is Y-4,
  124.         R is X+6,
  125.         B is Y+6,
  126.         draw(6,line(2,2),_),            % pensize 2
  127.         draw(12,oval(L,T,R,B),_),
  128.         path_pen_size(S),
  129.         draw(6,line(S,S),_).            % pensize Old
  130.  
  131. draw_square(P):-
  132.         xy(P,(X,Y)),
  133.         L is X-4,
  134.         T is Y-4,
  135.         R is X+6,
  136.         B is Y+6,
  137.         draw(6,line(2,2),_),            % pensize 2
  138.         draw(4,rect(L,T,R,B),_),
  139.         path_pen_size(S),
  140.         draw(6,line(S,S),_).            % pensize Old
  141.  
  142. init_pen_size :-
  143.         abolish(path_pen_size,1),
  144.  assert(path_pen_size(1)).
  145.  
  146. increment_pen_size :-
  147.         retract(path_pen_size(PS)),
  148.         NewPS is PS + 1,
  149.         draw(6,line(NewPS,NewPS),_),
  150.  assert(path_pen_size(NewPS)).
  151. %-------------------------------------------------------------------------